package demo.tree;

import java.util.Stack;

public class TreeUtil {
    public static void main(String[] args) {
        Node head = treeBuild();
        treePrint(head);

        System.out.println("非递归遍历");
        orderPreRecur(head);
        System.out.println();
        orderInRecur(head);
        System.out.println();
        orderPostRecur(head);
        System.out.println();
        System.out.println();

        System.out.println("递归遍历");
        orderPreUnRecur(head);
        orderInUnRecur(head);
        orderPostUnRecur(head);
        System.out.println();
        System.out.println();

        System.out.println("序列化树");
        System.out.println(serialPre(head));
        System.out.println();
        System.out.println();

        System.out.println("返回节点的后继节点");
        Node node = getSuccessorNode(head.left.right);
        System.out.println();
        System.out.println();

        System.out.println("");
        System.out.println("打印所有的纸质折痕信息");
        printAllFolds(3);
        System.out.println();
        System.out.println();
    }

    /**
     * 纸质对折，折痕问题  --跟节点是凹， 其他节点左凹右凸
     *
     * @param n
     */
    public static void printAllFolds(int n) {
        printProcess(1, n, true);
    }

    public static void printProcess(int i, int n, boolean down) {
        if (i > n) {
            return;
        }
        printProcess(i + 1, n, true);
        System.out.print(down ? "凹" : "凸");
        printProcess(i + 1, n, false);
    }

    /**
     * 给定二叉树的某个节点，返回该节点的后继节点
     */
    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return null;
        }

        if (node.right != null) {
            return getLeftMost(node.right);
        } else { //无右树
            Node parent = node.parent;
            while (parent != null && parent.left != node) {//当前节点是其父亲节点有孩子
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    /**
     * 获取最左的节点
     *
     * @param node
     * @return
     */
    public static Node getLeftMost(Node node) {
        if (node == null) {
            return null;
        }

        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 左旋的实现
     * p               pr
     * /\              /\
     * pl pr     =>    p  rr
     * /\          /\
     * rl rr       pl rl
     *
     * @param head
     */
    public static void RBTreeLeftRotate(Node head) {

    }

    public static String serialPre(Node head) {
        if (head == null) {
            return "#!";
        }

        String str = head.value + "!";
        str += serialPre(head.left);
        str += serialPre(head.right);
        return str;
    }


    public static void orderPostUnRecur(Node head) {
        if (head == null) {
            return;
        }

        //头右左
        //左右头
        Stack<Node> stack1 = new Stack<Node>();
        Stack<Node> stack2 = new Stack<Node>();
        stack1.push(head);
        while (!stack1.isEmpty()) {
            head = stack1.pop();
            stack2.push(head);
            if (head.left != null) {
                stack1.push(head.left);
            }

            if (head.right != null) {
                stack1.push(head.right);
            }
        }

        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value + "");
        }
    }

    public static void orderInUnRecur(Node head) {
        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.value + "");
                head = head.right;
            }
        }
        System.out.println();
    }

    public static void orderPreUnRecur(Node head) {
        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<Node>();
        stack.add(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            System.out.print(head.value + "");
            if (head.right != null) {
                stack.add(head.right);
            }

            if (head.left != null) {
                stack.add(head.left);
            }
        }
        System.out.println();
    }

    public static void orderPreRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head);
        orderPreRecur(head.left);
        orderPreRecur(head.right);
    }

    public static void orderInRecur(Node head) {
        if (head == null) {
            return;
        }
        orderInRecur(head.left);
        System.out.print(head);
        orderInRecur(head.right);
    }

    public static void orderPostRecur(Node head) {
        if (head == null) {
            return;
        }
        orderPostRecur(head.left);
        orderPostRecur(head.right);
        System.out.print(head);
    }

    public static void treePrint(Node head) {
        System.out.println("Binary Tree:");
        treePrintInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void treePrintInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }

        treePrintInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        treePrintInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer sb = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            sb.append(space);
        }
        return sb.toString();
    }

    public static Node treeBuild() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        return node1;
    }

    public static Node bstTreeBuild() {
        Node node1 = new Node(10);
        Node node2 = new Node(8);
        Node node3 = new Node(9);
        Node node4 = new Node(6);
        Node node5 = new Node(7);
        Node node6 = new Node(4);
        Node node7 = new Node(5);
        Node node8 = new Node(2);
        Node node9 = new Node(3);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        return node1;
    }
}
